{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Factorization machines"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Привет, друзья! Я хотел бы рассказать вам немного о концепте факторизационных машин, который в свое время меня впечатлил. Здесь не будет много строгой математики, однако мы рассмотрим предпосылки к появлению этой модели, и ее математические основы, а во второй части, конечно, немного попрактикуемся.\n",
    "\n",
    "На написание этого небольшого с позволения сказать тьюториала меня вдохновили и помогли [вот эта статья](https://www.csie.ntu.edu.tw/~b97053/paper/Rendle2010FM.pdf) и [лекции Евгения Соколова](https://www.youtube.com/watch?v=YmDT1hUTv2E) в CSClub."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Немного теории и предпосылок\n",
    "Хотя факторизационные машины могут применяться во всех задачах наравне с известными читателю моделями (линейными, деревьями, и т.д.), их основное достоинство - работа в условиях высокой разреженности данных (в дальнейшем станет понятно, почему). Поэтому, рассмотрим эту модель на примере задачи построения рекомендательной системы, реализации которых разной степени успешности вы можете встретить практически на любом ресурсе в наше время.\n",
    "<img src=\"../../img/fmtutor_rseverywhere.jpeg\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " Немного вне темы данной статьи скажу, что она будет относиться к так называемым [Контентным](https://en.wikipedia.org/wiki/Recommender_system#Content-based_filtering) моделям, которые в отличие от [Колаборативных](https://en.wikipedia.org/wiki/Recommender_system#Collaborative_filtering) моделей, допускают и опираются на дополнительные знания о товаре или покупателе, например, описание или историю посещений/покупок."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Итак, рассмотрим задачу рекомендации пользователям фильмов на некоем абстрактном ресурсе. Все просто - пользователи смотрят фильмы, и ставят им оценки от 1 до 5. Мы же хотим предсказывать оценку для новой пары пользователь-фильм, и, соответственно, если она высока, мы этот фильм пользователю рекомендуем. \n",
    "\n",
    "Закодируем информацию (создадим объекты выборки) следующим образом. Каждый пример будет вектором, условно поделенным на несколько частей:\n",
    "1. Идентификатор пользователя, являющийся результатом применения OheHot к идентификационному номеру пользователя, то есть это вектор, одна из координат которого равна 1, остальные - 0\n",
    "2. Идентификатор фильма - аналогично идентификатору пользователя из п. 1\n",
    "3. Любая другая полезная информация, как например: история просмотров, оценки другим фильмам, и проч."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Рассмотрим конкретнее:\n",
    "\n",
    "$ U = \\{Alice (A), Bob (B), Charlie (C), . . .\\} $ - множество пользователей\n",
    "\n",
    "$ I = \\{Titanic (TI) ,Notting Hill (NH),Star Wars (SW),Star Trek (ST), . . .\\} $ - множество фильмов\n",
    "\n",
    "$ S = \\{(A,TI,2010-1,5),(A,NH,2010-2,3),(A,SW,2010-4,1),(B,SW,2009-5,4),\n",
    "(B,ST,2009-8,5), . . . \\} $ - имеющиеся данные\n",
    "\n",
    "В виде матрицы:\n",
    "<img src=\"../../img/fmtutor_table.png\">\n",
    "Здесь синяя часть - активный юзер в данной транзакции, оранжевая - активный фильм, желтая - остальные фильмы, просмотренные юзером, зеленая - время в месяцах, начиная с января 2009 года, бордовая - последний просмотренный фильм. Не обязательно кодировать дополнительные признаки именно так, но важно следить, чтобы порядки значений не очень сильно отличались, потому что факторизационная машина многим похожа на линейную регрессию, а как читатель помнит из одной из статей курса, для такой модели важно, чтобы компоненты были примерно одного порядка."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Собственно, модель"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Итак, мы хотим обучить модель на этих данных. Фильмов у нас в базе много, а пользователей еще больше, мы ведь разрабатываем систему для популярного портала, не так ли? Поэтому на самом деле данные очень разрежены, и читатель уже знает, что, например, деревья плохо справятся с такой задачей, а вот линейные модели не должны встретить особых трудностей.\n",
    "\n",
    "Итак, первая наша идея - простая линейная модель:\n",
    "$$ \\hat{y} =  w_{0} + \\sum_{i = 1}^{n}w_{i}x_{i} $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Проблема такой модели в том, что она <b>не улавливает взаимодействий</b> между нашими сущностями. То есть простая линейная регрессия запомнит только то, что, скажем, Боб ставит обычно высокую оценку, а фильм NittingHill получает средние оценки."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Мы же хотим, чтобы модель выучивала еще и связи между людьми, фильмами и так далее. Ну так давайте их сделаем!\n",
    "$$ \\hat{y} = w_{0} + \\sum_{1}^{n}w_{i}x_{i} + \\sum_{i=1}^n\\sum_{j=i+1}^{n}w_{i,j}x_{i}x_{j} $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Уже лучше, модель должна выучить связи между всеми компонентами вектора примера. Однако внимательный читатель\n",
    "заметит основной недостаток такой модели - <b>число весов $ w_{i,j} $ растет пропорционально квадрату числа компонент в векторе</b>. Это большая проблема, потому что, например, число юзеров может запросто быть порядка миллиона, и, соответственно, порядок числа весов будет $ 10^{12} $, ну или еще больше. Это непозволительный расход памяти (если ее вообще столько найдется!)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Тогда упростим ее немного так, чтобы она не потеряла способности выучивать взаимодействия между компонентами, но в то же время не обладала таким гигантским числом параметров:\n",
    "$$ \\hat{y} = w_{0} + \\sum_{1}^{n}w_{i}x_{i} + \\sum_{i=1}^n\\sum_{j=i+1}^{n}\\langle v_{i}, v_{j} \\rangle x_{i}x_{j},$$\n",
    "где $$ w_{0} \\in \\mathbb{R}, w_{i} \\in \\mathbb{R}^{n}, v_{i} \\in \\mathbb{R}^{n\\times k},$$ a $ \\langle v_{i}, v_{j} \\rangle  = \\sum_{f=1}^{k}v_{i,f}\\cdot v_{j,f}$ - покомпонентное произведение векторов. (Да, для двух векторов это - скалярное произведение, но в дальнейшем мы обобщим это на случай большего числа векторов, поэтому используем это обозначение, и не будем его так называть)\n",
    "\n",
    "Итак, выше написано выражение для модели факторизационной машины степени $d = 2$, гиперпараметр $k$ отвечает за размерность факторизации. Степень 2 говорит о том, что модель выучивает одиночные и парные взаимодействия между компонентами вектора примеров.\n",
    "\n",
    "На самом деле, теоретический факт из линейной алгебры говорит о том, что при достаточно большом числе $k$ можно выразить все взаимодействия в исходной матрице, однако на практике лучше использовать небольшие значения этого гиперпараметра, так как во-первых, зачастую данных недостаточно для выражения сложных взаимодействий, а во-вторых ограничение $k$ уменьшает выразительную силу модели, и, как следствие, препятствует ее переобучению."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Следующий замечательный факт состоит в том, что вычисляется эта функция за $O(kn)$. Доказательство этого факта не сложно, но не хочется перегружать статью формулами, желающие могут найти его в [статье](https://www.csie.ntu.edu.tw/~b97053/paper/Rendle2010FM.pdf)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Заметим, что модель легко обобщается на случай произвольного числа степеней:\n",
    "$$ \\hat{y} = w_{0} + \\sum_{1}^{n}w_{i}x_{i} + \\sum_{l=2}^{d}\\sum_{i_{1} = 1}^{n}...\\sum_{i_{} = i_{l-1}+1}^{n}\\left ( \\prod_{j=1}^{l} x_{i_{j}}\\right )\\left ( \\sum_{f=1}^{k_{l}}\\prod_{j=1}^{l}v_{i_{j}, f}^{(l)} \\right ) $$\n",
    "На практике же обычно взаимодействия выше третьего порядка редко когда могут понадобиться, мне с ходу и не придумать такой пример :)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Если вернуться к нашей задаче с рекомендательно системой, то нам остается только выбрать гиперпараметры для модели (порядок и размерность), и предсказывать оценку как для обычной регрессионной задачи.\n",
    "\n",
    "Факторизационные машины можно использовать не только в задаче регрессии, но и для других, среди которых:\n",
    "1. Задача бинарной классификации (которая обобщается на случай многих классов элементарно с помощью алгоритмов OneVSOne или OneVSAll). Принадлежность к тому или иному классу определяется знаком $\\hat{y}$\n",
    "2. Задача ранжирования - входные векторы сортируются по соответствующему значению $\\hat{y}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Напоследок, переходя к практике, следует заметить также, что обычно в модель добавляют регуляризацию, например, $L2$ , чтобы также избежать переобучения.\n",
    "\n",
    "В соревнованиях на Kaggle, если задача была так или иначе связана с рекомендациями, эту модель очень часто можно встретить в решениях победителей ;)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Практика"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"../../img/fmtutor_theoryvspractice.png\" height=\"200\" width=\"300\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Я предлагаю рассмотреть небольшой пример работы факторизационной машины. Реализаций ее довольно много, я же хочу показать ту, которая мне показалась наиболее удобной и приятной (<b>важное замечание:</b> автор не видел <b>всех</b> реализаций, и еще не работал с реализаций FM от Vowpal Wabbit, и не исключает, что она тоже хороша!)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Единственный нюанс состоит в том, что реализация, которую я хочу показать требует установленной библиотеки [TensorFlow](https://github.com/tensorflow/tensorflow). Допускаю, что некоторые читатели еще не работали с ней - в рамках курса это нигде не потребовалось, но хорошая новость заключается в том, что сейчас нам не нужно разбираться, как она работает, ее просто нужно поставить. Автор хочет заверить читателя, что работать с этой библиотекой приется практически наверняка, если читатель планирует продолжать свои изыскания в области машинного обучения, поэтому ее установка не будет пустой тратой времени и ресурсов. Сейчас же она просто понадобится как бэкенд, поверх которого будеть работать наша факторизационная машина\n",
    "<img src=\"../../img/fmtutor_keras_backend.jpg\" height=\"100\" width=\"200\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Сама же реализация факторизационной машины [вот](https://github.com/geffy/tffm)\n",
    "\n",
    "Все вышеперечисленные библиотеки можно установать с помощью пакетного менеджера pip.\n",
    "\n",
    "Там же, в репозитории можно найти и пример, который мы сейчас рассмотрим. Мне не хотелось бы перегружать этот тьюториал большими данными, поэтому мы оставим такие задачи, как построение рекомендательной системы пользователю для самостоятельной практики, автор утверждает, что это возможно и весьма интересно:) А рассмотрим мы известный читаетелю датасет MNIST, и посмотрим, как модель будет различать, например тройки и пятерки"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Внимание!\n",
    "Если запуск следующей клетки приводит к ошибке AttributeError: module 'pandas' has no attribute 'computation', выполните команду <br>`pip install dask --upgrade` (или `conda update dask`). Или просто запустите ее еще раз - по какой-то причине так тоже работает"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import tensorflow as tf\n",
    "from sklearn.ensemble import RandomForestClassifier\n",
    "from sklearn.linear_model import LogisticRegression\n",
    "from sklearn.metrics import accuracy_score\n",
    "from sklearn.model_selection import train_test_split\n",
    "from tensorflow.examples.tutorials.mnist import input_data\n",
    "from tffm import TFFMClassifier\n",
    "from tqdm import tqdm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "mnist = input_data.read_data_sets(\"MNIST_data/\")\n",
    "\n",
    "mnist_images = mnist.train.images\n",
    "mnist_labels = mnist.train.labels\n",
    "\n",
    "n_three, n_five = sum(mnist_labels==3), sum(mnist_labels==5)\n",
    "\n",
    "X_all = np.vstack([\n",
    "    mnist_images[mnist_labels==3,:],\n",
    "    mnist_images[mnist_labels==5,:]\n",
    "])\n",
    "\n",
    "y_all = np.array([1]*n_three + [0]*n_five)\n",
    "# make it more sparse\n",
    "X_all = X_all * (np.random.uniform(0, 1, X_all.shape) > 0.8)\n",
    "\n",
    "print('Dataset shape: {}'.format(X_all.shape))\n",
    "print('Non-zeros rate: {:.05f}'.format(np.mean(X_all != 0)))\n",
    "print('Classes balance: {:.03f} / {:.03f}'.format(np.mean(y_all==0), np.mean(y_all==1)))\n",
    "\n",
    "X_tr, X_te, y_tr, y_te = train_test_split(X_all, y_all, random_state=42, test_size=0.3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Мы подготовили данные, давайте теперь посмотрим, как уже известные нам модели справляются с такой задачей, они будут нашими бейзлайнами:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for model in [\n",
    "                LogisticRegression(), \n",
    "                RandomForestClassifier(n_jobs=-1, n_estimators=200)\n",
    "            ]:\n",
    "    model.fit(X_tr, y_tr)\n",
    "    predictions = model.predict(X_te)\n",
    "    acc = accuracy_score(y_te, predictions)\n",
    "    print('model: {}'.format(model.__str__()))\n",
    "    print('accuracy: {}'.format(acc))\n",
    "    print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Посмотрим теперь, как справится фактоиризационная машина с этой задачей. Эта реализация поддерживает dense и sparse формат входа, мы рассмотрим второй, так как первый в принципе на него заменить можно, а вот наоборот в задачах с большими разреженными данными будет очень сложно"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import scipy.sparse as sp\n",
    "\n",
    "# only CSR format supported\n",
    "X_tr_sparse = sp.csr_matrix(X_tr)\n",
    "X_te_sparse = sp.csr_matrix(X_te)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Создадим модель FM третьего порядка (то есть улавливающую взаимодействия между единичными, парами и тройками объектов, в нашем случае - битов) и рангом (размерностью факторизации) - 30. Читателю предлагается поэкспериментировать с этими параметрами и посмотреть на изменение метрики и скорости обучения. Также в качестве гиперпараметров мы передаем число эпох, коэффициент регуляризации и т.д. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "order = 3\n",
    "model = TFFMClassifier(\n",
    "    order=order, \n",
    "    rank=30, \n",
    "    optimizer=tf.train.AdamOptimizer(learning_rate=0.001), \n",
    "    n_epochs=50, \n",
    "    batch_size=1024,\n",
    "    init_std=0.001,\n",
    "    reg=0.01,\n",
    "    input_type='sparse',\n",
    "    seed=42\n",
    ")\n",
    "model.fit(X_tr_sparse, y_tr, show_progress=True)\n",
    "predictions = model.predict(X_te_sparse)\n",
    "print('[order={}] accuracy: {}'.format(order, accuracy_score(y_te, predictions)))\n",
    "model.destroy()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Видим, что модель неплохо справилась с задачей, по крайней мере, бейзлайн мы побили:)\n",
    "\n",
    "Еще раз обращу внимание, что с повышением количества данных, их сложности и степени их разреженности, обычные модели станут работать намного хуже, а правильно настроенная и обученная факторизационная машина должна показывать неплохие результаты"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Это все, что я хотел вам рассказать, хотя, очень многие аспекты этой темы еще можно изучать как читателю, так и автору. Если вы имеете замечания по данному материалу, пожалуйста, напишите мне в слак или на почту - sergeygorbatyuk171@gmail.com, потому что я так же как и многие из вас еще в начале пути освоения этой интересной науки, а значит, могу допускать ошибки и неточности, давайте разбираться вместе!:) \n",
    "    \n",
    "    Спасибо большое, что уделили этому материалу ваше время!"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
